#ifndef __REMOVEELEMENT_H_
#define __REMOVEELEMENT_H_

#include <vector>
using namespace std;

/*
* leetcode 27 移除元素
* 给出一个元素, 移除在数组中相同的元素
* 
*/
/*
* 在正常的做法中, 直接使用容器的 erase 即可
* 
* 但是这样其实是效率不高的
* 
* 具体做法为用 后置元素 覆盖 被删除元素, 然后返回数组大小
* 即将被删除元素移至数组末尾
* 
* 这里使用 快慢指针(双指针) 来实现
* 慢指针 指向 被覆盖元素, 快指针 指向 覆盖元素
* 最终得到 [0, 慢指针] 范围的新数组
* 
* 例如:
* { 1, 2, 3, 4, 5, 6, 7, 8 }, target = 4
* return: 6  {1, 2, 3, 5, 6, 7, 8, 4}
*/
int RemoveElementWithDoublePointer(vector<int>& nums, int target) {
	int slow = 0, fast = 0;

	for (; fast < nums.size(); fast++) {
		//当 快指针 指向 被删除元素时, 快指针向前移动, 慢指针不动
		if (nums[fast] == target)
			continue;

		//当 快指针 没有指向 被删除元素时, 慢指针元素 赋值 快指针元素, 并且快慢指针向前移动
		else {
			nums[slow] = nums[fast];
			slow++;
		}
	}

	return slow;
}

#endif // !__REMOVEELEMENT_H_

